package Tree_09.HuffmanCode_06;

/*
 * @Author 罗
 * @date 2020/3/23 - 9:17 上午
 *
 */


import Tree_09.HuffmanTree_05.Node;


import java.util.*;

public class HuffmanCode {
    /*
     * Huffman编码表
     * */
    private static Map<Byte, String> huffmanCodeTable;

    /**
     * huffman编码 总方法
     *
     * @param contentBytes 原始数组
     * @return 编码后（压缩后的数组）
     */
    public static byte[] huffmanZip(byte[] contentBytes) {
        //1.使用Map<Byte,Integer>统计同一byte出现的次数
        Map<Byte, Integer> statisticCount = statisticsCharacterCount(contentBytes);
        //2.将map转为list集合，方便之后构建Huffman树
        List<MapNodeForByte> list = toNodes(statisticCount);
        //3.构建Huffman树，并且得到Huffman树的根节点
        MapNodeForByte root = constructHuffmanTree(list);
        //4.根据Huffman树生成Huffman编码表
        huffmanCodeTable = generateHuffmanCode(root);
        //5.使用Huffman编码表将原始byte[]数组编码，并返回
        return zip(contentBytes, huffmanCodeTable);
    }


    /**
     * 4.将字符串对应的byte[]数组，通过生成的Huffman编码表
     * 返回一个Huffman编码无损压缩后的byte[]
     *
     * @param bytes        需要编码的数据
     * @param huffmanCodes Huffman编码表，根据此编码表进行编码
     * @return
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        /*
         * 1.利用huffmanCodes 将 bytes 转成 huffman编码对应的字符串
         * */
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < bytes.length; i++) {

            stringBuilder.append(huffmanCodes.get(bytes[i]));
        }
        /*
         * 2.将huffman编码对应的字符串 转为 byte[]
         *       统计返回byte[] huffmanCodeBytes[]  的长度
         *       一行
         *   int length = (stringBuilder.length()+7)/8
         *       +7就是还原原来，要是有余数，+7除完进一位，效果和下面的一样
         * */
        int len;
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }

        /*System.out.println("原始数据byte[]长度" + bytes.length + "byte");
        for (byte aByte : bytes) {
            System.out.print(aByte + "\t");
        }
        System.out.println("\nHuffman编码后的长度" + len + "byte\t这里是二进制字符串表示\n" + stringBuilder.toString());
        */
        /*
         * 创建存储压缩后的byte数组
         * */
        byte[] huffmanCodeBytes = new byte[len];
        String temp;
        int index = 0;
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            /*
             * substring(int start,int end) 含头不含尾，end可以是stringBuilder的长度
             * 但是会可能取值到最后，位数不够8位，会导致越界异常
             *
             * */
            if (i + 8 > stringBuilder.length()) {
                /*
                 * substring(int start) 方法从开始位置到stringBuilder结尾截取字符串
                 * */
                temp = stringBuilder.substring(i);
            } else {
                temp = stringBuilder.substring(i, i + 8);
            }

            /*
             * parseInt(String s, int radix)根据radix(?进制)解析字符串
             *      编码后的单个八位，temp 是由多个字符他们各自的对应Huffman叶子节点的路径拼接而成的
             *      有时多个字符编码拼接后刚好构成8位，有时可能11位、其他位等等，但是不影响将其重新以8位截取为8为字符串，并拼接成新的byte[]
             * 以第一个temp为例，即temp = "10101000";
             * 转换为byte的步骤 temp存储在计算机中是以补码的形式存在
             *  因为10101000是负数，所以它的反码 = 10101000 - 1 = 10100111 ，原码 = 11011000 -> -88
             * 负数的反码 = 原码符号位不变，其余位取反；负数的补码 = 负数的反码+1
             * */
            huffmanCodeBytes[index] = (byte) Integer.parseInt(temp, 2);
            index++;
        }
        return huffmanCodeBytes;
    }


    /**
     * 通过Huffman树的根节点生成Huffman编码
     * 1.将Huffman编码表放在Map<Byte,String>中
     * byte存放的是一子节数据character对应的byte数据
     * String存储的是character数据被放置在Huffman树上，非叶子节点的路径 010101011010
     * 即，前缀编码
     * 为了方便调用，此方法对generateHuffmanCode()进行了重载
     *
     * @param root
     */
    private static Map<Byte, String> generateHuffmanCode(MapNodeForByte root) {
        if (root == null) {
            return null;
        }
        /*
         * 用于存储Huffman编码表
         * */
        Map<Byte, String> map = new HashMap<>();
        /*
         * 根节点上一级没有左右路径
         * 所以传入""
         * 把递归的操作完全叫个generateHuffmanCode()方法
         * */
//        generateHuffmanCode(root, new StringBuilder(), "", map);
//        相当于上面
//        给  generateHuffmanCode() 开个头，写好左右分支
        //处理root的左子树
        generateHuffmanCode(root.getLeft(), new StringBuilder(), "0", map);
        //处理root的右子树
        generateHuffmanCode(root.getRight(), new StringBuilder(), "1", map);

        /*
         * 以下是遍历部分

        Set<Map.Entry<Byte, String>> entrySet = map.entrySet();

        for (Map.Entry<Byte, String> byteStringEntry : entrySet) {
            System.out.println(byteStringEntry);
        }*/
        return map;
    }

    /**
     * 4.生成Huffman编码表
     *
     * @param temp    传入的节点
     * @param builder 用于放置拼接好了的路径
     * @param code    路径：左节点为0，右节点为1
     * @param map     用于存放Huffman编码表
     * @param <T>
     */
    private static <T extends Node> void generateHuffmanCode(T temp, StringBuilder builder, String code, Map<Byte, String> map) {

        if (temp == null) {
            return;
        }
        /*
         * 为了生成Huffman编码表示，需要去拼接路径
         * 为每一个叶子节点都去拼接路径
         *      每到一个二叉树（含左右节点的二叉树）就新建一个StringBuilder
         *      用于单独存放新节点的路径
         *
         *  如果为每一个分支创建StringBuilder，所有迭代都公用同一个StringBuilder
         *      因为对象是引用类型，迭代的时候使用的都是同一个指针
         * */
        StringBuilder builderForEachNode = new StringBuilder(builder);
        /*
         * 第一次拼接的时候，因为根节点不需要额外路径
         *   所以传入null，根节点不拼接
         *      直接传入""空字符串，就不用判断了
         * */
//        if (code != null) {
        builderForEachNode.append(code);
//        }
        /*
         * 没有存储数据的节点为非叶子节点
         *      继续递归
         *      非叶子节点只有权，没有Byte
         *      节点的数据必须是Byte类型而不是byte
         *      byte 不能为null，只能设置为0，但是0也是用来表示数据的
         * */
        if (((MapNodeForByte) temp).getData() == null) {

            if (temp.getLeft() != null) {

                generateHuffmanCode(temp.getLeft(), builderForEachNode, "0", map);

            }
            if (temp.getRight() != null) {

                generateHuffmanCode(temp.getRight(), builderForEachNode, "1", map);
            }
        } else {
            /*
             * 该节点有data数据，说明是叶子节点
             * Huffman树只有叶子节点才有数据
             * 已经抵达了叶子节点
             * */
            map.put(((MapNodeForByte) temp).getData(), builderForEachNode.toString());
        }
    }

    /**
     * 3.根据list构建Huffman树
     *
     * @param list
     * @return
     */
    private static MapNodeForByte constructHuffmanTree(List<MapNodeForByte> list) {
        while (list.size() > 1) {
            Collections.sort(list);
            MapNodeForByte leftNode = list.get(0);
            MapNodeForByte rightNode = list.get(1);
            /*
             * 非叶子节点的Huffman树只有权值，没有其他属性，比如byte
             * byte只能放在叶子节点
             * */
            MapNodeForByte parentNode = new MapNodeForByte(leftNode.getValue() + rightNode.getValue());
            parentNode.setLeft(leftNode);
            parentNode.setRight(rightNode);
            list.remove(leftNode);
            list.remove(rightNode);
            list.add(parentNode);
        }
        return list.get(0);
    }

    /**
     * 2.创建Huffman树的叶子节点对象
     * 把每一个key-value转成一个Node对象，并加入到List<MapNodeForByte>集合
     *
     * @param map
     * @return
     */
    private static List<MapNodeForByte> toNodes(Map<Byte, Integer> map) {
        List<MapNodeForByte> mapNodeForBytes = new LinkedList<>();
        Set<Byte> set = map.keySet();
        for (Byte aByte : set) {
            mapNodeForBytes.add(new MapNodeForByte(map.get(aByte), aByte));
        }
        return mapNodeForBytes;
    }

    /**
     * 1.统计相同byte出现的次数
     * 并将byte作为key，该byte出现的次数作为value
     * 放入Map<Byte,Integer>
     * 比直接统计每个字符出现的次数要好
     *
     * @param bytes
     * @return
     */
    private static Map<Byte, Integer> statisticsCharacterCount(byte[] bytes) {

        Map<Byte, Integer> map = new HashMap<>();

        for (int i = 0; i < bytes.length; i++) {
            if (map.get(bytes[i]) == null) {
                /*
                 * 当前map中不存在key == bytes[i] 的映射
                 * */
                map.put(bytes[i], 1);
            } else {
                /*
                 * map中已存在key == bytes[i] 的映射
                 * 直接+1
                 * */
                map.put(bytes[i], map.get(bytes[i]) + 1);
            }
        }
        return map;
    }

    /**
     * 给根节点，遍历Huffman树
     *
     * @param node
     * @param count
     * @param <T>
     */
    public static <T extends Node> void preOrderList(T node, int count) {
        count++;
        for (int i = 0; i < count; i++) {
            System.out.print("--");
        }
        System.out.println(node);
        if (node.getLeft() != null) {
            preOrderList(node.getLeft(), count);
        }
        if (node.getRight() != null) {
            preOrderList(node.getRight(), count);
        }
    }

    public static Map<Byte, String> getHuffmanCodeTable() {
        return huffmanCodeTable;
    }

    /**
     * Huffman压缩的详细过程
     *
     * @param str
     */
    public static void huffmanZipDetail(String str) {

        Map<Byte, Integer> map = HuffmanCode.statisticsCharacterCount(str.getBytes());

        Set<Byte> set = map.keySet();

        for (byte b : set) {
            System.out.println(b + "\t" + map.get(b));
        }

        List<MapNodeForByte> list = HuffmanCode.toNodes(map);

        for (MapNodeForByte mapNodeForByte : list) {
            System.out.println(mapNodeForByte);
        }

        MapNodeForByte root = HuffmanCode.constructHuffmanTree(list);
        System.out.println("前序遍历");
        HuffmanCode.preOrderList(root, 0);
        System.out.println("-------------->");
        Map<Byte, String> huffmanCodes = HuffmanCode.generateHuffmanCode(root);
        System.out.println("压缩----------->");
        byte[] huffmanCodeBytes = HuffmanCode.zip(str.getBytes(), huffmanCodes);
        System.out.println("最终Huffman编码的结果");
        for (byte huffmanCodeByte : huffmanCodeBytes) {
            System.out.print(huffmanCodeByte + "\t");
        }
    }
}
